package com.example.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

public class CQueue {

    Deque<Integer> deque1;
    Deque<Integer> deque2;

    public CQueue() {
        deque1 = new ArrayDeque<>();
        deque2 = new ArrayDeque<>();

    }

    public void appendTail(int value) {
        deque1.addFirst(value);
    }

    public int deleteHead() {
        if (deque1.isEmpty() && deque2.isEmpty()) {
            return -1;
        }
        if (!deque2.isEmpty()) {
            return deque2.removeFirst();
        }
        while (!deque1.isEmpty()) {
            deque2.addFirst(deque1.removeFirst());
        }
        return deque2.removeFirst();
    }
}

class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.fib(95));
        int[][] nums = {{1,2},{2,3}};
        System.out.println(solution.findNumberIn2DArray(nums,3));

    }

    public int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        long a = 0, b = 1;
        long ans = 0;
        long mo = 1000000007L;
        for (int i = 2; i <= n; i++) {
            ans = a + b;
            if(ans>mo){
                ans-=mo;
            }

            a = b;
            b = ans;

        }
        while(ans>mo){
           System.out.println(ans);
            ans-=mo;

        }
        System.out.println(ans);
        return (int) ans;
    }


    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int x=0,y=0;
        while(x<matrix[0].length&&y<matrix.length){
            if(matrix[x][y]==target){
                return true;
            }
            if(matrix[x][y]>target){
                x=x-1;
                y=y+1;
                continue;
            }
            x++;

        }
        return false;
    }
}